/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class FruitIntoBaskets {
	public int totalFruit(int[] tree) {
		HashMap<Integer, Integer> set = new HashMap<>();
		int i = 0;
		int j = 0;
		int max = 0;
		int type[] = new int[] { -1, -1 };

		while (i < tree.length) {
			while (i < tree.length && (set.containsKey(tree[i]) || set.size() < 2)) {
				set.put(tree[i], i);// 更新位置
				shiftType(type, tree[i]);
				i++;
			}
			int length = i - j;
			max = Math.max(max, length);
			if (i == tree.length)
				break;
			// j向前移动
			if (set.containsKey(type[0])) {
				j = set.get(type[0]) + 1;
				set.remove(type[0]);
			}
			set.put(tree[i], i);
			shiftType(type, tree[i]);

			i++;
		}
		return max;
	}

	/**
	 * 最近出现的三个不同的数 type[2]最近，type[0]最远
	 * 
	 * @param type
	 * @param i
	 */
	private void shiftType(int[] type, int i) {
		for (int j = 0; j < type.length; j++) {
			if (type[j] == -1) {
				type[j] = i;
				return;
			}
		}
		if (i == type[1])
			return;
		type[0] = type[1];
		type[1] = i;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] tree = { 3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4 };
		System.out.println(new FruitIntoBaskets().totalFruit(tree));
	}

}
